#include <iostream>

/* problem description 
* 
* The knight is placed on the empty board and, 
* moving according to the rules of chess, must visit each square exactly once. 
* 
* Here is the link to the original page: http://www.geeksforgeeks.org/archives/12916
*/
using namespace std;

#define N 7

//
// Define the board
//
int BOARD[N][N];

// Define the relative offset for knight move
int X[8] = {1,1,-1,-1,2,2,-2,-2};
int Y[8] = {2,-2,2,-2,1,-1,1,-1};

void InitBoard()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			BOARD[i][j] = -1;
		}
	}
}

void PrintBoard()
{
	for(int i=0; i<N; i++)
	{
		for(int j=0; j<N; j++)
		{
			cout<<BOARD[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}

bool IsSafeToMove( int x, int y)
{
	if(x<0 || x>=N || y<0 ||y>=N ||BOARD[x][y]!=-1)
		return false;
	return true;
}

bool VisitBoard( int x, int y, int curMove)
{
	if( curMove == N*N)
	{
		return true;
	}

	for( int i = 0; i<8; i++)
	{
		int newX = x+X[i];
		int newY = y+Y[i];
		if( IsSafeToMove(newX, newY))
		{
			BOARD[newX][newY] = curMove;
			if( VisitBoard(newX, newY, curMove+1))
			{
				return true;
			}
			BOARD[newX][newY]=-1;
		}
	}

	return false;
}

void VisitBoardAll( int x, int y, int curMove, int &sum)
{
	if( curMove == N*N)
	{
		sum++;
		cout<<"Find solution "<<sum<<endl;
		return;
	}

	for( int i = 0; i<N; i++)
	{
		int newX = x+X[i];
		int newY = y+Y[i];
		if( IsSafeToMove(newX, newY))
		{
			BOARD[newX][newY] = curMove;
			VisitBoardAll(newX, newY, curMove+1, sum);
			BOARD[newX][newY]=-1;
		}
	}
	return;
}

void VisitBoardStartEnd( int startX, int startY, int endX, int endY, int curMove, int &sum)
{
	int finalMove = N*N-1;
	if( curMove == finalMove+1)
	{
		sum++;
		cout<<"Find solution "<<sum<<endl;
		return;
	}

	for( int i = 0; i<N; i++)
	{
		int newX = startX+X[i];
		int newY = startY+Y[i];
		
		if(newX == endX && newY ==endY && curMove != finalMove)
			continue;
			
		if( IsSafeToMove(newX, newY))
		{
			BOARD[newX][newY] = curMove;
			VisitBoardStartEnd(newX, newY, endX, endY, curMove+1, sum);
			BOARD[newX][newY]=-1;
		}
	}
	return;
}

int main()
{
	int startX = 0;
	int startY = 0;
	int endX = N-1;
	int endY = N-1;
	bool findSolution = false;
	int sum = 0;
	
	InitBoard();

	//
	// Find the first solution then return
	//
	BOARD[startX][startY] = 0;
	findSolution = VisitBoard(startX, startY, 1);
	if(findSolution)
	{
		cout<<"Find a solution"<<endl;
		PrintBoard();
	}

	//
	// Find all solutions
	//
	InitBoard();
	sum = 0;
	BOARD[startX][startY] = 0;
	// comment out as it is too time consuming
	//VisitBoardAll(startX, startY, 1, sum);
	cout<<"Find "<<sum<<" solutions starting from ("<<startX<<","<<startY<<")"<<endl;

	//
	// Find all solutions start from and end with
	//
	InitBoard();
	sum = 0;
	BOARD[startX][startY] = 0;
	// comment out as it is too time consuming
	//VisitBoardStartEnd(startX, startY, endX, endY, 1, sum);
	cout<<"Find "<<sum<<" solutions starting from ("<<startX<<","<<startY<<") and end with ("<<endX<<","<<endY<<")"<<endl;

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}